package com.ljy.my_study.lintcode.骰子求和;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/** 
* @author James
* @date 2018年9月17日 
*/
public class TestMain {
//	描述
//	扔 n 个骰子，向上面的数字之和为 S。给定 Given n，请列出所有可能的 S 值及其相应的概率。
//
//	You do not care about the accuracy of the result, we will help you to output results.
//
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	给定 n = 1，返回 [ [1, 0.17], [2, 0.17], [3, 0.17], [4, 0.17], [5, 0.17], [6, 0.17]]。
	
//	我们假设有n个骰子，总的点数和为sum，那么在前面n-1个骰子的情况，最后一个可以有Sum-1、Sum-2、Sum-3、Sum-4、Sum-5、Sum-6的六种情况，而最后的那个骰子有下面的情况：
//	（n-1，sum-1）：第n个骰子扔出了1，等同n-1个骰子扔出了sum-1的情况。
//	（n-1，sum-2）：第n个骰子扔出了2，等同n-1个骰子扔出了sum-2的情况。
//	（n-1，sum-3）：第n个骰子扔出了3，等同n-1个骰子扔出了sum-3的情况。
//	（n-1，sum-4）：第n个骰子扔出了4，等同n-1个骰子扔出了sum-4的情况。
//	（n-1，sum-5）：第n个骰子扔出了5，等同n-1个骰子扔出了sum-5的情况。
//	（n-1，sum-6）：第n个骰子扔出了6，等同n-1个骰子扔出了sum-6的情况。

	
	public static void main(String[] args) {
		TestMain testMain=new TestMain();
		System.out.println(testMain.dicesSum(6));
	}
	
	public List<Map.Entry<Integer, Double>> dicesSum(int n) {
		long[][] dp=new long[n+1][6*n+1];          
		dp[1][1]=1;
		dp[1][2]=1;
		dp[1][3]=1;
		dp[1][4]=1;
		dp[1][5]=1;
		dp[1][6]=1;
		for(int i=2;i<=n;i++){              
			for(int j=i;j<=i*6;j++){                  
				long x1=0,x2=0,x3=0,x4=0,x5=0,x6=0;                  
				if(j-1>0){
					x1=dp[i-1][j-1];
					}
				if(j-2>0){ 
					x2=dp[i-1][j-2]; 
					}
				if(j-3>0){
					x3=dp[i-1][j-3];
					}
				if(j-4>0){
					x4=dp[i-1][j-4];   
					}
				if(j-5>0){
					x5=dp[i-1][j-5];   
					}
				if(j-6>0){
					x6=dp[i-1][j-6];
					}
				dp[i][j]=x1+x2+x3+x4+x5+x6;   
				}
			}
		List<Map.Entry<Integer, Double>> result=new ArrayList<Map.Entry<Integer,Double>>();  
		for(int i=n;i<=6*n;i++){
			AbstractMap.SimpleEntry<Integer, Double> entry=new AbstractMap.SimpleEntry<Integer, Double>(i, dp[n][i]/Math.pow(6, n));             
			result.add(entry);          
			}          
		return result;
	}
}
